# Definition for singly-linked list.
class ListNode:
    def __init__(self, x, n = None):
        self.val = x
        self.next = n

# 利用两个列表本来就已经有序的性质
class Solution:
    def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
        gen = self.__findMin(l1, l2)
        result, curr = None, None
        while True:
            try:
                v = next(gen)
                if curr == None:
                    curr = v
                    result = curr
                else:
                    curr.next = v
                    curr = curr.next
            except StopIteration:
                return result


    def __findMin(self, l1: ListNode, l2: ListNode) -> ListNode:
        li1, li2 = l1, l2
        while True:
            if li1 == None and li2 == None:
                return
            elif li1 == None:
                yield li2
                li2 = li2.next
            elif li2 == None:
                yield li1
                li1 = li1.next
            elif li1.val < li2.val:
                yield li1
                li1 = li1.next
            else:
                yield li2
                li2 = li2.next


list1 = ListNode(1, ListNode(2, ListNode(4)))
list2 = ListNode(1, ListNode(3, ListNode(4)))
solution = Solution()
result = solution.mergeTwoLists(list1, list2)

while result != None:
    print(result.val)
    result = result.next